<?php
function binSearch($x, $arr)
{
    $c = count($arr); //计算数组长度
    $lower = 0; //低位
    $high = $c - 1; //高位
    while ($lower <= $high) { //低位比高位低
        $middle = intval(($lower + $high) / 2); //中间值
        echo 'lower'.$lower.'------high'.$high.'------middle'.$middle.PHP_EOL;
        if ($arr[$middle] > $x) { //中间值比当前传递过来的值大
            $high = $middle - 1; //将高位赋值为当前位数
        } elseif ($arr[$middle] < $x) { //中间值比当前传递过来的值小
            $lower = $middle + 1; //低位赋值为当前位数
        } else {
            return $middle; //中间值等于传递过来的值的时候，返回当前的位置，就是要查找的位置
        }
    }
    return -1;
}

$arr = [1,2,3,4,5,6,7,9,11,12];

//echo binSearch(2,$arr);


function halfFind($x, $arr)
{
    $count = count($arr);
    $low = 0;
    $high = $count - 1;
    while ($low <= $high) {
        $middle = intval(($low + $high) / 2);
        if ($arr[$middle] > $x) {
            $high = $middle - 1;
        } elseif ($arr[$middle] < $x) {
            $low = $middle + 1;
        } else {
            return $middle;
        }
    }
    return -1;
}


function maoPao($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length - 1; $i++) {
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $t = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $t;
            }
        }
    }
    return $arr;
}


function change($arr)
{
    $count = count($arr);
    if ($count <= 0) {
        return false;
    }
    for ($i = 0; $i < $count - 1; $i++) {
        $minKey = $i;
        for ($j = $i; $j < $count; $j++) {
            if ($arr[$j] < $arr[$minKey]) {
                $minKey = $j;
            }
        }
        $t = $arr[$i];
        $arr[$i] = $arr[$minKey];
        $arr[$minKey] = $t;
    }
    return $arr;
}

function insert($arr)
{
    $count = count($arr);
    if ($count <= 0) {
        return false;
    }
    for ($i = 0; $i < $count; $i++) {
        $maxKey = $i - 1; //记录当前比前前面大的数据的键
        $maxValue = $arr[$i]; //记录当前比前面大的数据的值
        while ($maxKey >= 0 && $arr[$maxKey] > $maxValue) {
            $arr[$maxKey + 1] = $arr[$maxKey];
            $maxKey--;
        }
        $arr[$maxKey + 1] = $maxValue;
    }
    return $arr;
}

function erfen($x, $arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    $low = 0;
    $high = $length - 1;
    while ($low <= $high) {
        $middle = intval(($low + $high) / 2);
        if ($x > $arr[$middle]) {
            $low = $middle + 1;
        } else if ($x < $arr[$middle]) {
            $high = $middle - 1;
        } else {
            return $middle;
        }
    }
    return false;
}


function halfFind1($x, $arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return -1;
    }
    $min = 0;
    $max = $length - 1;
    while ($min <= $max) {
        $middle = intval(($min + $max) / 2);
        if ($arr[$middle] > $x) {
            $max = $middle - 1;
        } elseif ($arr[$middle] < $x) {
            $min = $middle + 1;
        } else {
            return $middle;
        }
    }
    return -1;
}

//echo halfFind1(0,$arr);

function maoPao1($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length - 1; $i++) {
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tem = $arr[$j+1];
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tem;
            }
        }
    }
    return $arr;
}
$noArr = [1,3,5,4,2,6,9,7,8,11,2];

function change1($arr)
{
    $length = count($arr);
    for ($i=0;$i<$length-1;$i++){
        $maxKey = $i;
        for ($j=$i;$j<$length;$j++){
            if ($arr[$j] > $arr[$maxKey]){
                $maxKey = $j;
            }
        }
        $tem = $arr[$i];
        $arr[$i] = $arr[$maxKey];
        $arr[$maxKey] = $tem;
    }
    return $arr;
}

function insert1($arr)
{
    $length = count($arr);
    if ($length<=0){
        return false;
    }
    for ($i = 0; $i < $length; $i++) {
        $key = $i - 1; //当前值的前一个键
        $value = $arr[$i];
        while ($key >= 0 && $arr[$key] > $value) {
            $arr[$key+1] = $arr[$key];
            $key--;
        }
        $arr[$key+1] = $value;
    }
    return $arr;
}

function quickSort($arr)
{
    $length = count($arr);
    if ($length <= 1) {//出口
        return $arr;
    }
    $left = $right = [];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] > $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    $leftArr = quickSort($left);
    $rightArr = quickSort($right);
    return array_merge($leftArr, [$arr[0]], $rightArr);
}

print_r(quickSort($noArr));